题解 P3582 【[POI2015]KIN】

发表于 | 更新于

$Description$

共有$m$部电影，编号为$1\sim m$，第$i$部电影的好看值为$w_{i}$。在$n$天之中(从$1\sim n$编号）每天会放映一部电影，第$i$天放映的是第$~f_{i}~$部。你可以选择$l,r(1\leqslant l\leqslant r\leqslant n)$，并观看第$l,l+1,\cdots,r$天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。

$Solution$

枚举右端点$r$，维护一个序列$c,$其中$c_l$表示$l\sim r$的好看值。对于一个位置$i$的好看值$w_i$，把他上一次出现的位置记做$pre_{i}$。由于如果有一个好看值$w_i$出现两次及以上，那么$w_i$的贡献为$0$,只有出现一次时才有贡献，显然只有在$pre_i+1\sim i$才会出现一次，所以当前$r$枚举到$i,c_{pre_i+1}\sim c_{i}+=w_i,$另外， 对于一个$~i~,pre_{pre_{i}}+1\sim pre_{i}$在上一个$j(w_{j}==w_{i})$时加上了一个$w_i$,但是对于$i,pre_{pre_{i}}+1\sim pre_{i}$区间中$w_i$的贡献为$0$,所以还有减去

这些操作考虑用线段树维护

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
#define re register
#define M 4000600
#define N 1000600
#define ls(k) (k<<1)
#define rs(k) (k<<1|1)
using namespace std;
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int ans,mx[M],tag[M],n,m,a[N],ma[N],pre[N],w[N];
inline void pushup(int k){
    mx[k]=max(mx[ls(k)],mx[rs(k)]);
}
inline void add(int k,int d){
    tag[k]+=d;
    mx[k]+=d;
}
void pushdown(int k){
    add(ls(k),tag[k]);add(rs(k),tag[k]);
    tag[k]=0;
}
void change(int k,int l,int r,int x,int y,int d){
    if (x<=l&&r<=y){
        add(k,d);
        return;
    }
    int mid=l+r>>1;
    if (tag[k])pushdown(k);
    if (x<=mid)change(ls(k),l,mid,x,y,d);
    if (mid<y) change(rs(k),mid+1,r,x,y,d);
    pushup(k);
}
int query(int k,int l,int r,int x,int y){
    if (x<=l&&r<=y)
        return mx[k];
    int mid=l+r>>1,res=0;
    if (tag[k])pushdown(k);
    if (x<=mid)res=max(res,query(ls(k),l,mid,x,y));
    if (mid<y) res=max(res,query(rs(k),mid+1,r,x,y));
    return res;
}
signed main(){
    n=read(),m=read();
    for (int i=1;i<=n;++i)a[i]=read();
    for (int i=1;i<=m;++i)w[i]=read();
    for (int i=1;i<=n;++i)
        pre[i]=ma[a[i]],ma[a[i]]=i;
    for (int i=1;i<=n;++i){
        change(1,1,n,pre[i]+1,i,w[a[i]]);
        if (pre[i])change(1,1,n,pre[pre[i]]+1,pre[i],-w[a[i]]);
        ans=max(ans,query(1,1,n,1,i));
    }
    printf("%lld\n",ans);
    return 0;
}